package org.example.myleet.p721;

import java.util.*;

public class Solution {
    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        //初始化，转换成账户模型
        List<Account> accList = new ArrayList<>(accounts.size());
        for (List<String> account : accounts) {
            Account acc = new Account();
            acc.name = account.get(0);
            for (int i=1; i<account.size(); i++) {
                acc.emails.add(account.get(i));
            }
            accList.add(acc);
        }
        UnionFind uf = new UnionFind();
        for (Account acc : accList) {
            //将每个节点加入到并查集中处理
            uf.union(acc);
        }
        Set<Account> result = new HashSet<>();
        //从并查集中获得每个根节点及其子节点的依赖关系
        Map<Account, Set<Account>> dependencies = uf.getDependencies();
        for (Account root : dependencies.keySet()) {
            //将子节点的所有邮箱合并到根节点上获得答案
            for (Account child : dependencies.get(root)) {
                root.emails.addAll(child.emails);
            }
            result.add(root);
        }
        List<List<String>> reply = new ArrayList<>(result.size());
        for (Account acc : result) {
            //将答案组装成对应的输出方式
            List<String> account = new ArrayList<>();
            account.add(acc.name);
            List<String> emailAddresses = new ArrayList<>(acc.emails);
            emailAddresses.sort(new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return o1.compareTo(o2);
                }
            });
            account.addAll(emailAddresses);
            reply.add(account);
        }
        return reply;
    }

    static class UnionFind {
        Map<Account, Account> parent;
        Map<String, Account> emailAccountMap;

        public UnionFind() {
            parent = new HashMap<>();
            emailAccountMap = new HashMap<>();
        }

        /**
         * 获得每个根节点及其子节点的依赖关系
         */
        public Map<Account, Set<Account>> getDependencies() {
            Map<Account, Set<Account>> dependencies = new HashMap<>();
            for (Account key : parent.keySet()) {
                Account root = find(key);
                dependencies.computeIfAbsent(root, k -> new HashSet<>()).add(key);
            }
            return dependencies;
        }

        /**
         * 查找某个节点的根节点
         */
        public Account find(Account account) {
            if (!parent.containsKey(account)) {
                parent.put(account, account);
                for (String email : account.emails) {
                    if (!emailAccountMap.containsKey(email)) {
                        emailAccountMap.put(email, account);
                    }
                }
                return account;
            }
            Account acc = parent.get(account);
            if (!acc.equals(account)) {
                parent.put(account, find(acc));
            }
            return parent.get(account);
        }

        /**
         * 将某个节点加入到并查集中
         */
        public void union(Account account) {
            //找到节点的根节点
            Account rootAcc = find(account);
            for (String email : account.emails) {
                //找到邮箱地址对应的节点及其根节点
                Account sameEmailAccount = emailAccountMap.get(email);
                Account sameEmailRootAccount = find(sameEmailAccount);
                if (!sameEmailRootAccount.equals(rootAcc)) {
                    //若两个根节点不是同一个，说明是出于两个不同的组中，则将两个组合并，并更新所有的邮箱指向同一个根节点
                    parent.put(sameEmailRootAccount, rootAcc);
                    parent.put(sameEmailAccount, rootAcc);
                    emailAccountMap.put(email, rootAcc);
                    for (String e : sameEmailAccount.emails) {
                        emailAccountMap.put(e, rootAcc);
                    }
                    for (String e : sameEmailRootAccount.emails) {
                        emailAccountMap.put(e, rootAcc);
                    }
                }
            }
        }
    }

    static class Account {
        String name;
        Set<String> emails;

        public Account() {
            this.emails = new HashSet<>();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Account account = (Account) o;
            return name.equals(account.name) &&
                    emails.equals(account.emails);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name, emails);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Account{");
            sb.append("name='").append(name).append('\'');
            sb.append(", emails=").append(emails);
            sb.append('}');
            return sb.toString();
        }
    }
}
